package com.zhanghp.class033;

/**
 * 不用任何算术运算，只用位运算实现加减乘除<br/>
 * 代码实现中你找不到任何一个算术运算符
 * 测试链接 : https://leetcode.cn/problems/divide-two-integers/
 *
 * @author zhanghp
 * @since 2024/4/10 9:45
 */
public class BitOperationAddMinusMultiplyDivide {

    public static final int MIN = Integer.MIN_VALUE;

    public static void main(String[] args) {
        System.out.println(multiply(5, 2));
        int a = 0b1011;
        int b = 0b10110;
        int c = 0b101100;
        System.out.println(a + b + c);
        int d = 0b1011;
        int e = 0b0111;
        System.out.println(e * d);
        System.out.println(1 / 11);
        System.out.println(false);
        System.out.println(true);
        System.out.println(div2(1, 2));
        System.out.println(div2(2, 2));
        System.out.println(div2(3, 2));

        System.out.println(divide(-2147483648, 1));
    }

    public static int divide(int a, int b) {
        if (a == MIN && b == MIN) {
            return 1;
        }
        if (a != MIN && b != MIN) {
            return div(a, b);
        }
        // 还剩2中情况
        // a为最小，b不为
        // a不为，b为最小

        // b为最小，a不为最小
        if (b == MIN) {
            return 0;
        }
        // a是整数最小，b是-1，返回整数最大，因为题目里明确这么说了
        if (b == neg(1)) {
            return Integer.MAX_VALUE;
        }
        // 现在就剩a是最小值，b不是最小值的情况了
        int x = add(a, b > 0 ? b : neg(b));
        int ans = div(x, b);
        int offset = b > 0 ? neg(1) : 1;
        return add(ans, offset);

    }

    /**
     * 两数相除（必须保证a和b都不是整数最小值，返回a除以b的结果）
     * <p>
     * 280 / 25 = 11
     * <p>
     * 280 = 25 * 2<sup>3</sup> + 25 * 2<sup>1</sup> + 25 * 2<sup>0</sup>
     *
     * @param a
     * @param b
     * @return
     */
    public static int div(int a, int b) {
        int x = a > 0 ? a : neg(a);
        int y = b > 0 ? b : neg(b);
        int ans = 0;
        // 为什么不是31？因为移动31位，比较的是符号位
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((x >>> i) >= y) {
                x = minus(x, y << i);
                ans |= 1 << i;
            }
        }
        return a > 0 ^ b > 0 ? neg(ans) : ans;
    }

    public static int div2(int a, int b) {
        int x = a > 0 ? a : neg(a);
        int y = b > 0 ? b : neg(b);
        int ans = 0;
        for (int i = 0; i < 30; i = add(i, 1)) {
            if ((x >>> i) >= y) {
                x = minus(x, y << i);
                ans |= 1 << i;
            }
        }
        return a > 0 ^ b > 0 ? neg(ans) : ans;
    }

    /**
     * 加
     * <p>
     * 1011<br/>
     * 0111<br/>
     * 先看最右侧1×上面的二进制，然后第二个1，第三个1，最后加起来<br/>
     * 1011 + 10110 + 101100
     *
     * </p>
     *
     * @param a
     * @param b
     * @return
     */
    public static int add(int a, int b) {
        int ans = a;
        while (b != 0) {
            ans = a ^ b;
            b = (a & b) << 1;
            a = ans;
        }
        return ans;
    }

    /**
     * 减
     *
     * @param a
     * @param b
     * @return
     */
    public static int minus(int a, int b) {
        return add(a, neg(b));
    }

    public static int multiply(int a, int b) {
        int ans = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                ans = add(ans, a);
            }
            b >>>= 1;
            a <<= 1;

        }
        return ans;
    }

    /**
     * 取反
     *
     * @param a
     * @return
     */
    public static int neg(int a) {
        return add(~a, 1);
    }

}
